// javamaps
// Copyright (c) 2010 Lup Gratian
package Rendering.Utils;
import java.util.*;
import Core.*;

public class LineSimplifier {
    private static void SimplifyImpl(List<Point> points, int startPoint,
                                     int endPoint, double minDistanceSq,
                                     List<Point> selected) {
        double startX = points.get(startPoint).X();
        double startY = points.get(startPoint).Y();
        double endX = points.get(endPoint).X();
        double endY = points.get(endPoint).Y();
        double maxDistSq = 0;
        int index = -1;

        for(int i = startPoint + 1; i < endPoint; i++) {
            double distance = LineUtils.PointLineDistanceSq(points.get(i),
                                              startX, startY, endX, endY);
            if(distance > maxDistSq) {
                maxDistSq = distance;
                index = i;
            }
        }

        // Daca distanta este suficient de mare se incearca simplificarea
        // pe regiuniile aflate la stanga si la dreapta punctului gasit.
        if(maxDistSq >= minDistanceSq) {
            if((index - startPoint) >= 2) {
                SimplifyImpl(points, startPoint, index,  minDistanceSq, selected);
            }

            // Se adauga punctul gasit.
            selected.add(points.get(index));
            
            if((endPoint - index) >= 2) {
                SimplifyImpl(points, index, endPoint, minDistanceSq, selected);
            }
        }
    }

    // Alege o serie de puncte folosind algoritmul Douglas-Peucker
    // astfel incat sa se pastreze precizia specificata.
    // http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
    public static void Simplify(List<Point> points, double minDistance,
                                List<Point> selected) {
        assert(points != null);
        assert(minDistance >= 0);
        assert(selected != null && points.size() >= 2);
        // ------------------------------------------------
        // Primul si ultimul punct sunt intotdeauna incluse.
        selected.add(points.get(0));
        SimplifyImpl(points, 0, points.size() - 1, minDistance * minDistance, selected);
        selected.add(points.get(points.size() - 1));
    }
}